This program uses code from the AIMA git repository (https://github.com/aimacode/aima-python/) to simulate a vacuum cleaner "cleaning" the environment using an A* searching algorithm.
States are defined using a list containing the world and location of the agent. The world is represented by a list containing 1's and 0's representing dirty and clean squares respectively. The location is a value 0-9 representing the agents location with in the world and references an index of the world list.
Currently the initial state is a hard-coded world containing 3 dirty squares on the top row and a starting loction of index 4 for the agent. There is, however, code with can be uncommented that will generate random worlds and starting positions for the agent.
In [161]:
from search import Problem
import random
class VacuumProblem(Problem):
def __init__(self):
# Uncomment the line below to generate random worlds and starting locations
#initial_state = ([random.randrange(0,2) for i in range(0,9)], random.randrange(0,9))
# This line contains the hard-coded world and starting location.
initial_state = [[1,1,1,0,0,0,0,0,0], 4]
goal_state = [ [[0,0,0,0,0,0,0,0,0], i] for i in range(0,9)]
super().__init__(initial_state, goal_state)
def actions(self, state):
loc = state[1]
if state[0][loc] == 1:
return ["SUCK"]
elif loc == 0:
return ["DOWN", "RIGHT"]
elif loc == 3:
return ["UP", "DOWN", "RIGHT"]
elif loc == 6:
return ["UP", "RIGHT"]
elif loc == 1:
return ["DOWN", "LEFT", "RIGHT"]
elif loc == 4:
return ["UP", "DOWN", "LEFT", "RIGHT"]
elif loc == 7:
return ["UP", "LEFT", "RIGHT"]
elif loc == 2:
return ["DOWN", "LEFT"]
elif loc == 5:
return ["UP", "DOWN", "LEFT"]
elif loc == 8:
return ["UP", "LEFT"]
else:
return ["FAILURE"]
def result(self, p_state, action):
world = list(p_state[0])
loc = p_state[1]
state = []
state.append(world)
state.append(loc)
if action is "SUCK":
state[0][state[1]] = 0
return state
elif action is "LEFT":
state[1] -= 1
return state
elif action is "RIGHT":
state[1] += 1
return state
elif action is "UP":
state[1] -= 3
return state
elif action is "DOWN":
state[1] += 3
return state
def path_cost(self, cur_cost, state1, action, state2):
if action is "SUCK":
new_cost = abs(-2 * state2[0].count(1) -1)
cost = cur_cost + new_cost
return cost
else:
new_cost = abs(-2 * state1[0].count(1) -1)
cost = cur_cost + new_cost
return cost
def goal_test(self, state):
for g in self.goal:
if g == state:
return True
def h(self, n):
h_cost = 0
min_dist = 10000000
num_actions = 0
dirty = 0
pos = n.state[1]
count = 0
for s in n.state[0]:
if s == 1:
dirty += 1
dist = abs(pos - count)
if min_dist > dist:
min_dist = dist
count += 1
num_actions = min_dist + 1
h_cost = dirty + min_dist + num_actions
return h_cost
In [162]:
from search import *
def best_first_graph_search(problem, f):
"""Search the nodes with the lowest f scores first.
You specify the function f(node) that you want to minimize; for example,
if f is a heuristic estimate to the goal, then we have greedy best
first search; if f is node.depth then we have breadth-first search.
There is a subtlety: the line "f = memoize(f, 'f')" means that the f
values will be cached on the nodes as they are computed. So after doing
a best first search you can examine the f values of the path returned."""
f = memoize(f, 'f')
node = Node(problem.initial)
if problem.goal_test(node.state):
return(node)
frontier = PriorityQueue(min, f)
frontier.append(node)
explored = []
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return(node)
explored.append(node.state)
for child in node.expand(problem):
if child.state not in explored and child not in frontier:
frontier.append(child)
elif child in frontier:
incumbent = frontier[child]
if f(child) < f(incumbent):
del frontier[incumbent]
frontier.append(child)
return None
def astar_search(problem, h=None):
"""A* search is best-first graph search with f(n) = g(n)+h(n).
You need to specify the h function when you call astar_search, or
else in your Problem subclass."""
h = memoize(h or problem.h, 'h')
node = best_first_graph_search(problem, lambda n: n.path_cost + h(n))
return(node)
VP = VacuumProblem()
n = astar_search(VP)
for p in n.path():
print(p, 'Action: {!s:5s} Path Cost: {}'.format(p.action, p.path_cost))